﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Middle_34_SearchRange
{
    class MainProject
    {
        static void Main(string[] args)
        {
            int[] array = new int[]
            {
              5,7,7,8,8,10
            };
            foreach (var item in SearchRange(array, 5))
            {
                Console.WriteLine(item);
            }
            //Console.WriteLine(IsPalindrome(1000021));
            Console.ReadKey();
        }
        public static int[] SearchRange(int[] nums, int target)
        {

            int[] array = new int[] { -1, -1 };
            if (nums.Length == 0) return array;

            int lastIndex = 0;
            int nextIndex = nums.Length - 1;
            int middleIndex = 0;
            while (lastIndex <= nextIndex)
            {
                middleIndex = (lastIndex + nextIndex + 1) / 2;
                if (nums[middleIndex] < target)
                {
                    lastIndex = middleIndex + 1;
                }
                else if (nums[middleIndex] > target)
                {
                    nextIndex = middleIndex - 1;
                }
                else
                {
                    int record = middleIndex;
                    while (true)
                    {
                        if (record >= 0 && nums[record] == target)
                        {
                            record--;
                        }
                        else
                        {
                            array[0] = record + 1;
                            break;
                        }
                    }
                    record = middleIndex;
                    while (true)
                    {
                        if (record < nums.Length && nums[record] == target)
                        {
                            record++;
                        }
                        else
                        {
                            array[1] = record - 1;
                            break;
                        }
                    }
                    break;
                }
            }
            return array;
        }
    }
}
